import java.util.*;

/*
快速幂
给定n组a_i, b_i, p_i，对于每组数据，求出a_i^b_i mod p_i的值。

输入格式
第一行包含整数n，接下来n行，每行包含三个整数a_i, b_i, p_i。

输出格式
对于每组数据，输出一个结果，表示a_i^b_i mod p_i的值，每个结果占一行。

数据范围
1 ≤ n ≤ 100000，1 ≤ a_i, b_i, p_i ≤ 2 × 10^9。

输入样例为：
2
3 2 5
4 3 9
输出样例为：
4
1
 */
//public class Main {
//    static long binPow(long a, long b, long p) {
//        long res = 1;
//        while (b > 0) {
//            if ((b & 1) == 1) {
//                res = res * a % p;
//            }
//            b >>= 1;
//            a = a * a % p;
//        }
//
//        return res;
//    }
//
//    public static void main(String[] args) {
//        Scanner sc = new Scanner(System.in);
//        int n = sc.nextInt();
//        while (n-- > 0) {
//            System.out.println(binPow(sc.nextLong(), sc.nextLong(), sc.nextLong()));
//        }
//    }
//}

/*
快速幂求逆元

给定 n 组 a_i，p_i，其中 p_i 是质数，求 a_i 模 p_i 的乘法逆元，若逆元不存在则输出 impossible。
注意：请返回在 0～p-1 之间的逆元。

乘法逆元的定义
若整数 b，m 互质，并且对于任意的整数 a，如果满足 b|a，则存在一个整数 x，使得 a / b ≡ a × x (mod m)，则称 x 为 b 的模 m 乘法逆元，记为 b^{-1} mod m。
b 存在乘法逆元的充要条件是 b 与模数 m 互质。当模数 m 为质数时，b^{m-2} 即为 b 的乘法逆元。

输入格式
第一行包含整数 n。
接下来 n 行，每行包含一个数组 a_i，p_i，数据保证 p_i 是质数。

输出格式
输出共 n 行，每组数据输出一个结果，每个结果占一行。
若 a_i 模 p_i 的乘法逆元存在，则输出一个整数，表示逆元，否则输出 impossible。

数据范围
1 ≤ a_i，p_i ≤ 2 * 10^5，
1 ≤ a_i，p_i ≤ 2 * 10^9

输入样例：
3
4 3
8 5
6 3

输出样例：
1
2
impossible
 */

public class Main {
    static long binPow(long a, long b, long p) {
        long res = 1;
        while (b > 0) {
            if ((b & 1) == 1) res = res * a % p;
            a = a * a % p;
            b >>= 1;
        }
        return res;
    }

    static long gcd(long a, long b) {
        return b > 0 ? gcd(b, a % b) : a;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        for (int i = 0; i < n; i++) {
            long a = sc.nextLong(), p = sc.nextLong();
            if (gcd(a, p) > 1) System.out.println("impossible");
            else System.out.println(binPow(a, p - 2, p));
        }
    }
}
